Atcoder ABC396游记

Atcoder ABC396游记（A~E）

A.Triple Four

题目描述

给你一个长度为$N$的数组$A$，问你有没有$3$个连续且相同的元素？

思路

感觉不用讲

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 2; i++) {
        if (a[i] == a[i + 1] && a[i + 1] == a[i + 2]) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

B.Card Pile

题目描述

给你一个栈，最初有$100$个$0$在里面。支持$2$种操作：

• 1 x往栈顶放一个元素$x$。

• 2输出栈顶元素，并且把栈顶元素移除。

思路

感觉不用讲

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    stack<int> st;
    for (int i = 1; i <= 100; i++) {
        st.push(0);
    }
    int q;
    cin >> q;
    while (q--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int x;
            cin >> x;
            st.push(x);
        } else {
            cout << st.top() << '\n';
            st.pop();
        }
    }
    return 0;
}

C.Buy Balls

题目描述

有$N$个白球，$M$个黑球，每个球上面都写了一个数。

第$i$个白球上面写的数字是$W_i$。

第$i$个黑球上面写的数字是$B_i$，

思路

贪心就刑 好奇有没有用dp做出来的神犇

没错但是我还是被这题卡了一下 但是问题不大

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> b(n);
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    sort(b.rbegin(), b.rend());
    vector<ll> w(m);
    for (int i = 0; i < m; ++i) {
        cin >> w[i];
    }
    sort(w.rbegin(), w.rend());
    vector<ll> b_sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        b_sum[i] = b_sum[i - 1] + b[i - 1];
    }
    vector<ll> w_sum(m + 1, 0);
    for (int i = 1; i <= m; ++i) {
        w_sum[i] = w_sum[i - 1] + w[i - 1];
    }
    vector<ll> maxB(n + 1);
    maxB[n] = b_sum[n];
    for (int k = n - 1; k >= 0; --k) {
        maxB[k] = max(b_sum[k], maxB[k + 1]);
    }
    ll res = 0;
    int max_t = min(m, n);
    for (int t = 0; t <= max_t; ++t) {
        ll current = w_sum[t] + maxB[t];
        if (current > res) {
            res = current;
        }
    }
    cout << res;
    return 0;
}

D.Minimum XOR Path

题目描述

给你一个简单的连通无向图，包含 $N$ 个顶点，编号从 $1$ 到 $N$，以及 $M$ 条边，编号从 $1$ 到 $M$。边 $i$ 连接顶点 $u_i$ 和 $v_i$，并且具有标签 $w_i$。

在从顶点 $1$ 到顶点 $N$ 的所有简单路径（即不经过相同顶点超过一次的路径）中，找到路径上边的标签的最小异或值。

关于异或（XOR）的说明： 对于非负整数 $A$ 和 $B$，它们的异或 $A \oplus B$ 定义如下：

在 $A \oplus B$ 的二进制表示中，对应于 $2^k ,(k \ge 0)$ 的位为 $1$ 当且仅当 $A$ 和 $B$ 的相同位置的位中恰好有一个为 $1$；否则，该位为 $0$。
例如，$3 \oplus 5 = 6$（在二进制中：$011 \oplus 101 = 110$）。 一般而言，$k$ 个整数 $p_1, \dots, p_k$ 的异或定义为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$。可以证明，它不依赖于 $p_1, \dots, p_k$ 的顺序。

思路

你看，你看这个$N$啊，才最大到$10$，真的太逊了

时间限制也是$2$秒，也是很逊啊

所以不用想太多，直接DFS

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector<vector<pair<int, int>>> edges;
int ans;
void dfs(int u, int cur, int vis) {
    if (u == n) {
        if (cur < ans) {
            ans = cur;
        }
        return;
    }
    for (const auto& edge : edges[u]) {
        int v = edge.first;
        int w = edge.second;
        if (!(vis & (1 << v))) {
            int nex = vis | (1 << v);
            int nexx = cur ^ w;
            dfs(v, nexx, nex);
        }
    }
}
signed main() {
    cin >> n >> m;
    edges.resize(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].emplace_back(v, w);
        edges[v].emplace_back(u, w);
    }
    ans = LLONG_MAX;
    dfs(1, 0, 1 << 1);
    cout << ans;
    return 0;
}

E.Min of Restricted Sum

题目描述

给你整数 $N$ 和 $M$，以及三个长度为 $M$ 的整数序列：$X = (X_1, X_2, \ldots, X_M)$，$Y = (Y_1, Y_2, \ldots, Y_M)$，和 $Z = (Z_1, Z_2, \ldots, Z_M)$。保证 $X$ 和 $Y$ 中的所有元素都在 $1$ 到 $N$ 之间（包括 $1$ 和 $N$）。

我们称一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$ 为好序列，当且仅当它满足以下条件：

对于每一个整数 $i$，满足 $1 \le i \le M$，$A_{X_i}$ 和 $A_{Y_i}$ 的异或值等于 $Z_i$。
判断是否存在一个好序列 $A=(A_1,A_2,\ldots,A_N)$，如果存在，找到一个好序列，使其元素之和 $\displaystyle \sum_{i=1}^N A_i$ 最小。

关于异或（XOR）的说明： 对于非负整数 $A$ 和 $B$，它们的异或 $A \oplus B$ 定义如下：

在 $A \oplus B$ 的二进制表示中，对应于 $2^k ,(k \ge 0)$ 的位为 $1$ 当且仅当 $A$ 和 $B$ 的相同位置的位中恰好有一个为 $1$；否则，该位为 $0$。
例如，$3 \oplus 5 = 6$（在二进制中：$011 \oplus 101 = 110$）。

思路

我们搞一个并查集维护它到父节点的异或路径。

如何判断是不是$-1$？我们可以通过在输入约束的时候同时用并查集判断有没有矛盾。

然后我们从高位到低位确定答案，保证小

然后，我不知道该写啥

代码

#include<bits/stdc++.h>
using namespace std;
vector<int> fa;
vector<int> xorp;
void init(int n) {
    fa.resize(n);
    xorp.resize(n, 0);
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
    }
}
int find(int x) {
    if (fa[x] != x) {
        int orfa = fa[x];
        fa[x] = find(fa[x]);
        xorp[x] ^= xorp[orfa];
    }
    return fa[x];
}
bool unite(int x, int y, int z) {
    int rx = find(x);
    int ry = find(y);
    int xorx = xorp[x];
    int xory = xorp[y];
    if (rx == ry) {
        return (xorx ^ xory) == z;
    } else {
        fa[rx] = ry;
        xorp[rx] = xorx ^ xory ^ z;
        return true;
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> x(m), y(m), z(m);
    for (int i = 0; i < m; ++i) {
        cin >> x[i] >> y[i] >> z[i];
        x[i]--;
        y[i]--;
    }
    init(n);
    bool flag = true;
    for (int i = 0; i < m; ++i) {
        if (!unite(x[i], y[i], z[i])) {
            flag = false;
            break;
        }
    }
    if (!flag) {
        cout << -1;
        return 0;
    }
    unordered_map<int, vector<int>> groups;
    for (int i = 0; i < n; ++i) {
        find(i);
        int root = fa[i];
        groups[root].push_back(i);
    }
    vector<long long> a(n, 0);
    for (auto& [root, nodes] : groups) {
        vector<int> cnt0(31, 0), cnt1(31, 0);
        for (int i : nodes) {
            int x = xorp[i];
            for (int k = 0; k < 31; ++k) {
                if ((x >> k) & 1) {
                    cnt1[k]++;
                } else {
                    cnt0[k]++;
                }
            }
        }
        long long root_val = 0;
        for (int k = 30; k >= 0; --k) {
            if (cnt1[k] >= cnt0[k]) {
                root_val |= (1LL << k);
            }
        }
        for (int i : nodes) {
            a[i] = root_val ^ xorp[i];
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << a[i] << ' ';
    }
    return 0;
}

总结

我不知道写啥啊

来娱乐亿下

一个TB的oier写的文章

原作者

原文洛谷链接

本站链接

今天是38妇女节，祝每一位妇女节日快乐，rp++！

（怎么写的书面一点我不到啊）